package leetcode_jz_offer.day9;

/**
 * 某单元格只可能从上边单元格或左边单元格到达。
 * 设f(i, j)为从棋盘左上角走至单元格(i ,j)的礼物最大累计价值
 * 易得到以下递推关系：f(i,j)f(i,j) 等于 f(i,j-1)f(i,j−1) 和 f(i-1,j)f(i−1,j) 中的较大值加上当前单元格礼物价值 grid(i,j)grid(i,j) 。
 * f(i,j)=max[f(i,j−1),f(i−1,j)]+grid(i,j)
 **/

/**
 * 状态方程
 * 当 i=0 且 j=0 时，为起始元素；最大价值就是当前单元格礼物价值；dp(i,j)=grid(i,j)
 * 当 i=0 且 j!=0时，为矩阵第一行元素，只可从左边到达；dp(i,j)=grid(i,j)+dp(i-1,j);
 * 当 i!=0且 j=0 时，为矩阵第一列元素，只可从上边到达；dp(i,j)=grid(i,j)+dp(i,j-1);
 * 当 i !=0 且 j!=0 时，可从左边或上边到达dp(i,j)=grid(i,j)+max(dp(i,j-1),dp(i-1,j));
 */
public class Num47_礼物的最大价值 {
    public int maxValue(int[][] grid) {
        int m=grid.length;//行
        int n= grid[0].length;//遍历列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(i==0&&j==0){
                    //其实元素，最大价值就是当前格元素的礼物价值
                    continue;
                } else if(i==0){
                    //一行
                    grid[i][j]=grid[i][j]+grid[i][j-1];
                } else if(j==0){
                    //一列
                    grid[i][j]=grid[i][j]+grid[i-1][j];
                } else {
                    grid[i][j]=grid[i][j]+Math.max(grid[i-1][j],grid[i][j-1]);
                }

            }
        }
        return grid[m-1][n-1];
    }
}
